package com.lht.leetcodeDemo;

import org.junit.Test;

/**
 * @author Eric
 * @version 1.0
 * @date 2019-05-17
 */
public class MergeTwoLists {

    @Test
    public void test() {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        ListNode l11 = l1.next;
        l11.next = new ListNode(4);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        ListNode l22 = l2.next;
        l22.next = new ListNode(4);
        ListNode node = new MergeTwoLists().headMergeTwoLists(l1, l2);
        while (node != null) {
            System.out.print(node.val + ",");
            node = node.next;
        }
    }

    /**
     * <p>
     * 合并两个有序列表
     * 递归:
     * 1. 先给header赋值
     * 2. 递归的给header.next 赋值
     *
     * 这样 header 链就形成了
     * 因为递归关系，最后返回的依然是header首位，会递归到第一层返回
     * 这个方法确实 6666
     * </p>
     *
     * @param l1 链表1
     * @param l2 链表2
     * @return com.lht.leetcodeDemo.MergeTwoLists.ListNode
     * @throws
     * @author Eric
     * @date 2019/5/22
     **/
    public ListNode recursionMergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode header = null;
        if (l1.val <= l2.val) {
            header = l1;
            header.next = recursionMergeTwoLists(l1.next, l2);
        } else {
            header = l2;
            header.next = recursionMergeTwoLists(l1, l2.next);
        }
        return header;
    }
    /**
     * @author Eric
     * @date 2019/5/27
     * @param l1 1
     * @param l2 2
     * @return com.lht.leetcodeDemo.MergeTwoLists.ListNode
     * @throws
     **/
    public ListNode headMergeTwoLists(ListNode l1, ListNode l2) {
        //new 一个链表节点作为头
        ListNode dump = new ListNode(0);
        //将头的引用赋值给另外一个变量，这里意义就是 头的引用不会变，变得只是这个引用
        ListNode cur = dump;
        while(l1 != null || l2 != null) {
            if(l1 == null) {
                cur.next = l2;
                l2 = l2.next;
            }else if (l2 == null) {
                cur.next = l1;
                l1 = l1.next;
            }else if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return dump.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}



